package com.gitee.wsl.func.filter.sample

import com.gitee.wsl.lang.bits.BitSet
import com.gitee.wsl.security.hash.HasherFactory
import com.gitee.wsl.security.hash.MD5
import com.gitee.wsl.security.hash.SHA1
import kotlin.math.*

/**
 *
 * Bloom Filter数据结构实现
 *
 * @author Letcheng on 2016/2/23.
 */
open class BloomFilter<E> {
    var bitSet: BitSet
        protected set
    protected var m: Int //Bloom Filter的位数

    /**
     *
     * 当Bloom Filter满的时候，每个元素占的位数，通过构造方法进行设置
     * @return
     */
    var c: Double //每个元素的位数
        protected set

    /**
     * 获取Bloom Filter可以插入的最大元素
     * @return
     */
    var nMax: Int //Bloom Filter最大的元素个数
        protected set

    protected var n: Int // Bloom Filter实际元素的个数

    var k: Int // hash函数的个数
        protected set


    /**
     * @param c
     * @param n_max
     * @param k
     */
    constructor(c: Double, n_max: Int, k: Int) {
        this.nMax = n_max
        this.k = k
        this.c = c
        this.m = ceil(c * n_max).toInt()
        n = 0
        this.bitSet = BitSet(m)
    }

    constructor(m: Int, n_max: Int, k: Int) {
        this.nMax = n_max
        this.k = k
        this.m = m
        this.c = 1.0 * m / n_max
        n = 0
        this.bitSet = BitSet(m)
    }

    /**
     *
     * 根据m和n_max计算k的最优值
     * 根据论文的推导：k = lg2*(m/n_max)
     * @param m
     * @param n_max
     */
    constructor(m: Int, n_max: Int) : this(
        m / n_max.toDouble(),
        n_max,
        round((m / n_max.toDouble()) * ln(2.0)).toInt()
    ) //k = log2*(m/n_max)


    /**
     * 最常用的构造方法
     * @param fpp
     * @param n_max
     */
    constructor(fpp: Double, n_max: Int) : this(
        ceil(-(ln(fpp) / ln(2.0))) / ln(2.0),  // c = k / ln(2)
        n_max,
        ceil(-(ln(fpp) / ln(2.0))).toInt()
    ) // k = ceil(-lg_2(fpp))


    /**
     * 计算在插入最大元素的情况下的误判率
     * @return
     */
    fun maxFpp(): Double {
        return getFpp(nMax.toDouble())
    }

    /**
     * 根据当前的元素计算误判率
     * @param n
     * @return
     */
    fun getFpp(n: Double): Double {
        // (1 - e^(-k * n / m)) ^ k
        return (1 - exp(
            -k * n
                    / m.toDouble()
        )).pow(k.toDouble())
    }

    val fpp: Double
        /**
         * 计算当前元素个数的误判率
         * @return
         */
        get() = getFpp(n.toDouble())


    /**
     * 重置Bloom Filter
     */
    open fun clear() {
        bitSet.clear()
        n = 0
    }

    /**
     *
     * 添加对象到Bloom Filter中，会调用对象的toString()方法作为Hash方法的输入
     * @param element
     */
    fun add(element: E) {
        add(element.toString().encodeToByteArray())
    }

    /**
     * 添加字节数组到Bloom Filter中
     * @param bytes
     */
    open fun add(bytes: ByteArray) {
        val hashes = createHashes(bytes, k)
        for (hash in hashes) bitSet[abs(hash % m)] = true //使用K个Hash函数映射到1位

        n++ //添加了一个元素
    }

    /**
     * 添加一个对象集合到Bloom Filter中
     * @param c
     */
    fun addAll(c: Collection<E>) {
        for (element in c) add(element)
    }

    /**
     *
     * 获取某个对象是否已经插入到Bloom Filter中，可以使用getFpp()方法计算结果正确的概率
     *
     * @param element
     * @return
     */
    fun contains(element: E): Boolean {
        return contains(element.toString().encodeToByteArray())
    }

    /**
     * 判定某个字节数组是否已经插入到Bloom Filter中，可以使用getFpp()方法计算结果正确的概率
     * @param bytes
     * @return
     */
    fun contains(bytes: ByteArray): Boolean {
        val hashes = createHashes(bytes, k)
        for (hash in hashes) {
            if (!bitSet[abs(hash % m)]) { //如果有一位未设置，则该元素未插入，但是返回true，并不代表这个元素一定插入过，即存在误判率的概念。
                return false
            }
        }
        return true
    }

    /**
     * 如果有一个元素未被插入到Bloom Filter中，则返回false
     * @param c elements to check.
     * @returnr.
     */
    fun containsAll(c: Collection<E>): Boolean {
        for (element in c) if (!contains(element)) return false
        return true
    }

    /**
     * 获取Bloom Filter中某一位的值
     * @param bit
     * @return
     */
//    fun getBit(bit: Int): Boolean {
//        return bitSet[bit]
//    }

    /**
     * 设置Bloom Filter每一位的值
     * @param bit
     * @param value true代表该位已经被设置，false代表未进行设置
     */
//    fun setBit(bit: Int, value: Boolean) {
//        bitSet.set(bit, value)
//    }

    /**
     * 获取当前的位数
     * @return
     */
    fun size(): Int {
        return this.m
    }

    /**
     * 获取当前的插入的元素的个数
     * @return
     */
    fun count(): Int {
        return this.n
    }

    val bitsPerElement: Double
        /**
         * 获取当前情况下，Bloom Filter实际上每个元素占的位数
         * @return
         */
        get() = this.m / n.toDouble()

    companion object {

        //在大多数情况下MD5准确率较好，也可以选择SHA1
        //const val hashName: String = "MD5"

        /**
         *
         * 根据Hash的个数，生成散列值
         * @param data
         * @param hashes
         * @return
         */
        fun createHashes(data: ByteArray, hashes: Int, digestFunction: HasherFactory = MD5): IntArray {
            val result = IntArray(hashes)

            var k = 0
            var salt: Byte = 0

            while (k < hashes) {
                val hasher = digestFunction()
                hasher.update(salt)
                salt++
                hasher.update(data)
                val digest: ByteArray = hasher.digest().bytes

                var i = 0
                while (i < digest.size / 4 && k < hashes) {
                    var h = 0
                    for (j in (i * 4)..<(i * 4) + 4) {
                        h = h shl 8
                        h = h or ((digest[j].toInt()) and 0xFF)
                    }
                    result[k] = h
                    k++
                    i++
                }
            }
            return result
        }
    }
}